COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂25-Oct-86  1410	KMP@STONY-BROOK.SCRC.Symbolics.COM 	Your turn
C00023 00003	/sub
C00075 00004	∂08-Nov-86  0013	willc%tekchips.tek.csnet@RELAY.CS.NET 	Re: Draft  
C00140 00005	/sub
C00153 ENDMK
C⊗;
∂25-Oct-86  1410	KMP@STONY-BROOK.SCRC.Symbolics.COM 	Your turn
Received: from SCRC-STONY-BROOK.ARPA by SAIL.STANFORD.EDU with TCP; 25 Oct 86  14:10:30 PDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 142728; Sat 25-Oct-86 17:10:19 EDT
Date: Sat, 25 Oct 86 17:08 EDT
From: Kent M Pitman <KMP@SCRC-STONY-BROOK.ARPA>
Subject: Your turn
To: RPG@SU-AI.ARPA
cc: KMP@SCRC-STONY-BROOK.ARPA
Message-ID: <861025170843.9.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

Ok, I've exhausted all the time I have to work on this today and you
should have a go at it before it gets too well-formed anyway. Please feel
free to fill out things or change the order or wording. Obviously I have
a saved draft and can compare anything you send back with it to find out
what you've done.

I started off by assuming there would be two parts to section 3 --
advantages and disadvantages, but that looked like it'd be too hard on
the reader who would feel like he'd seen two separate documents, so I
decided to merge them and assume that the arguments would be more
intimately intertwined. You can change it back if you disagree.

I'm using a stripped down form of Scribe that Zmacs understands with the
m-X Format Buffer command, so if you have a 3600 around, that's the
recommended way to get this typed out. c-U m-X Format Buffer will let
you output it to a hardcopy device. Presumably Scribe will also mostly
like it if I didn't screw up and do @foo(@bar(...)) instead of
@foo(@bar[...])  so that it's stupid little parser can deal. If the formatter
is a problem, change it to what you like. I'm sure I can change it back
easily enough while I play with it.

I'd like to get this back in a week or so. Good luck, and drop me a line
if you have any questions about the parts that aren't fully detailed...

-----Text of Paper Follows-----
@center(@b[Issues of Separation in Function Cells and Value Cells])

@center(@b[by RPG and KMP, etc.])

@b(1. Introduction)

Motivation ... The Europeans in [what?] have suggested that we should
[something specific goes here].

The Common Lisp community is currently studying the issue. Here are some
questions we might want to answer:
 Is it technically feasible to change things?
 What is the cost/benefit of making the change?
 What is the cost/benefit of having made the change?

Before attempting to make any decision on the subject, the Common Lisp
community felt it important to clearly document both sides of the issue
in an unbiased way.

@b(2. Background)

[Perhaps some text here about how and why the separation arose originally
in case it was for different reasons than why it survived. Perhaps, too,
some text about what happened in languages like Scheme where the separation
did not arise.]

@b(3. Issues)

@b(3.1 Notational Simplicity)

Many people believe that having the function position be evaluated
differently than the argument positions in Lisp is very inelegant.

This feature has the indirect effect of making the notation more
complicated in order to allow two things -- looking up a function
to call using the rules for variable evaluation and looking up an
argument to pass using the rules for functional evaluation.

To call a function which is the value of a variable (or the result
of some other normally evaluated expression), you currently must use
the @t(FUNCALL) function. For example, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
@End(Example)
If functions and arguments were evaluated the same, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
@End(Example)

To pass an argument which is obtained by the rules of functional
evaluation, you currently must use the @t(FUNCTION) special form.
For example, one might write:
@Begin(Example)
(MAPC #'PRINT '(A B C D))
@End(Example)
If functions and arguments were evaluated the same, one might write:
@Begin(Example)
(MAPC PRINT '(A B C D))
@End(Example)

Probably few people would deny that the syntax resulting from the this
change would make the language appear better visually. If the issue were
being decided purely on the basis of cosmetics, probably few people
would oppose the change. Resistance to change by some members of the
Common Lisp community is generally based in the implications of the
change on current and future code, rather than in some claim that there
is no visual appeal to this simpler syntax.

@b(3.2 Multiple denotations for a single name)

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose you have defined a function @t(F) as:
@Begin(Example)
(DEFUN F (X) (+ X 1))
@End(Example)
Then suppose you are writing a new function @t(G) and you want it to
take a functional parameter @t(F) which it is to apply to its other argument.
Suppose you wrote:
@Begin(Example)
(DEFUN G (F) (F 3))
@End(Example)
Issues of defined program semantics aside, it's obvious that the programmer
who wrote this piece of code meant to call the function named by the formal
parameter @t(F) on the argument @t(3). The semantics of present day Common 
Lisp are more complicated because they define this expression to involve
a globally defined function named @t(F) which the programmer is trying to call 
and a local parameter named @t(F) which the programmer is trying to ignore.

Unfortunately, not all situations are as clear cut as this. For example, 
in the following example:
@Begin(Example)
(DEFUN PRINT-SQRTS (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)
In this example, there are three uses of the name @t(LIST). The first is in
the bound variable list. The second is in initialization of the @t(DOLIST) 
variable. The third is in the @t(PRINT) expression. This program, which is
valid in current Common Lisp, would not be valid in a Common Lisp where 
functional and argument positions were evaluated in the same way. A common
thing to write instead would be:
@Begin(Example)
(DEFUN PRINT-SQRTS (LST)
  (DOLIST (ELEMENT LST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)

As should be clear from these examples, the advantage of treating the function
and argument positions the same is that using parameters as functions is made
more syntactically convenient.

The disadvantage is that @i(not) using parameters as functions is made
syntactically less convenient since parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions which will be needed in the function body.

[My sense here is that this is what identifies the issue as essentially 
an axiomatic one and not one which can be proven (or disproven) as 
elegant/inelegant in some absolute terms. I'd like to work that in here
somehow. -KMP]

If you're looking for a very simple example of this phenomenon to discuss on 
a napkin over dinner, here it is:
@Begin(Example)
(DEFUN ODDITY-1 (LIST) (LIST LIST LIST))
(ODDITY #'CONS)
@End(Example)
Depending on which way the issue is decided, the possible return values from
this function are:
@Begin(Example)
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
@End(Example)

@b(3.3 Number of Namespaces)

We shouldn't try to kid ourselves about the level of simplicity that will
be achieved by this change. Merging function cells and value cells doesn't
mean that every time you see a symbol, you can uniquely determine its 
meaning with no sense of context. Symbols will still have special meanings
when interpreted as types, declarations, etc.

@b(3.4 Macros and Name Collisions)

[I need to write lots more here, of course.]

Consider:

@Begin(Example)
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO THINGS))
...
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
@End(Example)

or:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
...
(DEFMACRO TEST-CAR (CAR TEST-LIST)
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
@End(Example)

People have discussed, and IBM folks claim [I need to dig up a reference to this]
to have implemented, the ability to write:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(',CAR ,LIST))
@End(Example)

This is syntactically more tedious and that would have to be weighed.
Nevertheless, it doesn't answer all technical problems. In particular,
their implementation works by getting the value of CAR at loadtime.
It doesn't address what happens if you do:

@Begin(Example)
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))
(FOO 3 Z)
@End(Example)

since there is no function at loadtime to get. You have to output all
the code which supports the anonymous closure which the compiler finds
at runtime. This would have to be done recursively through all the functions
called by the indicated function, a problem which is recursively unsolvable
in general unless the entire compilation environment can be statically closed
over, which could be impossibly expensive in general.

@b(3.5 Space Efficiency)

If a name is used as both a variable and a function, it currently costs no
additional space. Any program which has symbols which are used to denote 
distinct functions and values, however, would have to be changed. In general,
this mean that some new symbols would be introduced. In most cases, the number
of new symbols introduced would not be extremely large, but there might be
pathological applications where there were exceptions.

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to ...

Resolving the name conflicts that would result if functions
and variables were in the namespace would require the creation of additional
symbols.


@b(3.6 Time Efficiency)

In VAXLISP, the function cell is checked for call validity at SETF execution 
time to make sure that a jump to it without checking will be ok at call time.


@b(3.7 Cultural Compatibility)

We have encouraged the naming convention of *...* around global names.
To make functions and values the same would be to say that this convention
was then a somewhat gratuitous distinction.

@b(3.8 Special Variable Warnings)

Functions would want to be non-special, but would want to not be warned
about when used free. Normally, you have to declare variables SPECIAL to
get this behavior. This would result in lower error checking.

@b(3.9 Compatibility Issues)

Making a transition to a world with unified a function/value cell would
involve a considerable amount of incompatibility.

@b(3.9.1 Changing existing code)

Large bodies of code already exist which make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which is not trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100% reliability in any automatic way.

@b(3.9.2 Compatibility packages)

Various compatibility schemes have been proposed which would allow these
problems to be hacked by compatibility packages ... [RPG: do you know what they
are? Steele was mentioning this idea to me but I didn't get the details. In
any case, I think the argument in the next paragraph will still apply if you can
expand this.]

The problem is that the compilers and other program-understanding programs
might be fooled by such compatibility things. For example, such programs
may have built-in assumptions about the function cell and value cell being
distinct and may not realize that a store into the value cell in one place
will perturb a later access to the function cell, which it may believe it has
proven could not be changed in a certain interval of code.

@b(3.10 Compatibility with Scheme)

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. On the other hand, if all other things are equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

However, all other things are not equal. For example, there is an installed
base of code which would require changing. There are reasons to believe that
the change would not be gratuitous. 

Even if compatibility with Scheme was achieved on this point, there is
currently no iron-clad guarantee that Scheme will not later change in an
incompatible way that will thwart such a good faith move on the part of 
Common Lisp. It is an explicit goal of the Scheme designers [ref R↑3 Report]
that Common Lisp compatibility not be uppermost in the list of concerns.
That should weigh in.

@b(4. Summary)

[When we get close to done, perhaps we can do a quick one or two sentence
recap of the pros and cons [that word looks funny in lispy literature].]

/sub
"edsel!lnz"@navajo
Draft
Here it is, though it is not well-proofread. I't is a partial
Scribe format.
			-rpg-

@center(@b[Issues of Separation in Function Cells and Value Cells])

@center(@b[by RPG and KMP, etc.])

@b(0. Notation and Terminology) 

In this white paper we will use the following terminology. A `function' is
anything that can be APPLYed or FUNCALLed. A `non-function' is any other
Lisp object. We say that `a function, F, is associated with the symbol, S'
to mean that a pointer to the functional object, F, is stored in the
symbol-function cell of the symbol, S. We say that `a function, F, is
associated with the variable, V' to mean that a pointer to the function,
F, is stored as the value of the binding for the variable, V, and that the
variable, V, is meaningful only in a functional setting (the car position
of a combination or as the argument of FUNCTION). Functions become
associated with variables using FLET, LABELS, and MACROLET only. Functions
become associated with symbols using DEFUN and (SETF (SYMBOL-FUNCTION
...)...). We say that `a symbol or a variable, SV, has as its value the
function, F' to mean that the value cell of the symbol, SV, or the value
part of the binding for the variable, SV, contains a pointer to the
function, F.

The `functional position' of a combination is the first element in a list
that is to be used as an expression to evaluate or to compile. (Other people
say that the functional position is `the car of the form.')

A `name' is either a symbol or a variable.

A `namespace' is a mapping between names and objects.  There are two
namespaces with which we are concerned: the functional namespace and the
value namespace. To be particular, given a name which names a function,
the functional namespace is the mapping that yields the function named by
the name; given a name which names a value, the value namespace is the
mapping that yields the value associated with the name.  The functional
and value namespaces are distinct because, give a single name, the
functional namespace mapping and the value namespace mapping can yield
distinct objects. Note, the two namespaces might yield the same object,
but for definitional purposes, this happenstance is coincidental.

The functional namespace mapping is from names to functions; the value
namespace mapping is from names to Lisp objects, which includes functions.

The domain of the functional namespace also includes forms which look like
this:

	(lambda ...)

The functional namespace mapping is (FUNCTION <name>) and can be abbreviated
as #'<name>.

The value namespace mapping is (EVAL <form>). Lambda-expressions are not
in the domain of the value namespace mapping in Common Lisp.

@b(1. Introduction)

In 1981 the emerging Common Lisp community turned to Scheme for some of
its motivation and inspiration. Adopting lexical scoping proved one of the
most important decisions the Common Lisp group every made.  One aspect of
Scheme left behind was the unification of the function and value
namespaces.

The Common Lisp community is now faced with the fact of the existence of
three Lisp communities:  Common Lisp, Scheme, and EuLisp. The latter two
communities have adopted a unified function and value namespace; Common
Lisp has not. The question is whether it is feasible at this point for the
Common Lisp community to change its stand on this point - to merge the two
namespaces - and to merge the Lisp communities.

Before attempting to make any decision on the subject, the Common Lisp
community felt it important to clearly document both sides of the issue
in an unbiased way.

@b(2. Background)

Historically, most Lisp dialects have adopted a 2-namespace approach to
the naming problem. Largely this is because most dialects followed Lisp 1.5
unless there was some interesting reason not to follow it.

In Lisp 1.5, functions could be defined be LABEL or be associated with a
symbol. LABEL is like Common Lisp LABELS, and it was used to define
recursive functions which were associated with variables exactly as
values were associated with variables - on an a-list. McCarthy says that
LABEL was used infrequently, because functions were put on the property
lists of symbols, under a property name like SUBR. The terminology in the
Lisp 1.5 Programmer's Manual is that a ``symbol stands for a function.''

On the other hand, Lisp 1.5 had nothing like FUNCALL; MAPLIST was defined
like this:

(DEFUN MAPLIST (X FN)
 (COND ((NULL X) NIL)
       (T (CONS (FN X) (MAPLIST (CDR X) FN)))))

In our terminology, Lisp 1.5 had two distinct namespaces, but they
coincided on the domain of variables. That is, given a variable as a name,
the value namespace mapping and the function namespace mapping are
identical.

@b(3. Technical Reasons for the Merger)

@b(3.1 Notational Simplicity)

Many people believe that having the function position be evaluated
differently than the argument positions in Lisp is very inelegant.

This feature has the indirect effect of making the notation more
complicated in order to allow two things:  1. taking a name, using the
value namespace mapping to yield a value which happens to be a function,
and invoking that function; 2. taking a name, using the function namespace
mapping to yield a function, and using that function exactly like any
other Lisp object.

To call a function which is the value of a variable (or the result
of some other normally evaluated expression), one must use
the @t(FUNCALL) function. For example, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
@End(Example)
In a single namespace Lisp, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
@End(Example)

To pass an argument which is obtained by the rules of functional
evaluation, you currently must use the @t(FUNCTION) special form.
For example, one might write:
@Begin(Example)
(MAPC (FUNCTION PRINT) '(A B C D))
@End(Example)
or
@Begin(Example)
(MAPC #'PRINT '(A B C D))
@End(Example)
If there were a single namespace, one might write:
@Begin(Example)
(MAPC PRINT '(A B C D))
@End(Example)
The differences are more striking in a larger, more complex
example. In Common Lisp one writes:
@BEGIN(Example)
(DEFUN Y (F)
 (LET ((G #'(LAMBDA (H)
             #'(LAMBDA (Z)
                (FUNCALL (FUNCALL F (FUNCALL H H)) Z)))))
  #'(LAMBDA (X)
     (FUNCALL (FUNCALL F (FUNCALL G G)) X))))
@END(Example)
while in a single namespace Common Lisp, one would write:
@BEGIN(Example)
(DEFUN Y (F)
 (LET ((G (LAMBDA (H)
           (LAMBDA (Z) 
            ((F (H H)) Z)))))
  (LAMBDA (X) ((F (G G)) X))))
@END(Example)
which anyone can see is much simpler.

Probably few people would deny that the syntax resulting from the this
change would make the language appear better visually. If the issue were
being decided purely on the basis of cosmetics, probably few people
would oppose the change.

@b(3.2 Multiple Denotations for a Single Name)

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose a programmer has defined a function @t(F) as:
@Begin(Example)
(DEFUN F (X) (+ X 1))
@End(Example)
Then suppose he is writing a new function @t(G) and he wants it to
take a functional parameter @t(F) which it is to apply to its other argument.
Suppose he writes:
@Begin(Example)
(DEFUN G (F) (F 3))
@End(Example)
Issues of defined program semantics aside, it's probably obvious that the
programmer who wrote this piece of code meant to call the function named
by the formal parameter @t(F) on the argument @t(3). 
In Common Lisp, this function will ignore its arguement named @t(F) and
simply invoke the globally defined function named @t(F) on 3.

Unfortunately, not all situations are as clear cut as this. For example, 
in the following example:
@Begin(Example)
(DEFUN PRINT-SQRTS (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)
In this example, there are three uses of the name @t(LIST). The first is in
the bound variable list. The second is in initialization of the @t(DOLIST) 
variable. The third is in the @t(PRINT) expression. This program, which is
valid in current Common Lisp, would not be valid in a Common Lisp where 
functional and argument positions were evaluated in the same way. A common
thing to write instead would be:
@Begin(Example)
(DEFUN PRINT-SQRTS (LST)
  (DOLIST (ELEMENT LST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)

As should be clear from these examples, the advantage of treating the
function and argument positions the same is that using parameters as
functions is made more convenient syntactically.

The disadvantage is that @i(not) using parameters as functions is made
less convenient syntactically, because parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions which will be needed in the function body.

In the function PRINT-SQRTS above, the parameter named LST is better named
LIST, though PRINT-SQRTS is not better named PRINT-SQUARE-ROOTS.

The following is a simple example of some of the important issues 
in variable naming:
@Begin(Example)
(DEFUN ODDITY-1 (LIST) (LIST LIST LIST))
(ODDITY #'CONS)
@End(Example)
Depending on which way the issue is decided, the possible return values from
this function are:
@Begin(Example)
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
@End(Example)

@b(3.3 Higher Order Functions are Possible)

Functions like the Y function above, which manipulate functions directly, are
more perspicuously written within a single namespace Lisp. The point is that
with two namespaces this style is not encouraged, while in a single namespace
Lisp it is encouraged.

@b(3.4 Abstraction Sharing)

In a single namespace Lisp, it is easier to define an abstract piece of
code that shares abstractions between data and functions. An example of
this is the abstract stream code in Chapter 4 of Abelson and Sussman, in
which it is shown how to write streams based either on functions or on data
structures.  Again, all of this is possible in Common Lisp as it stands,
but it is not an encouraged style. The problem is that it is a burden to
think about which namespace mapping will be in force for various
variables.

@b(3.5 Compiler Simplicity)

In current Common Lisp compilers, special cases code is used when
deciding which namespace mapping to use when a variable is
examined by the compiler. A single namespace Lisp will result in simpler,
smaller, faster compilers in some cases.

@b(3.6 Referential Clarity)

In a 2-namespace Lisp it is the case that without a context it is not
possible to decide whether the functional or the value namespace is the
proper one to use. These two forms result in different interpretations of
x:
@BEGIN(Example)
(x ...)
@END(Example)
@BEGIN(Example)
(... x ...)
@END(Example)
Unfortunately, the basic rule of Lisp style is violated, that rule being
that code is clear when the least amount of context is necessary to
determine what each expression does.

@b(3.7 Multiprocessing)

The functional style which is encouraged by single namespace Lisps
is conducive to multiprocessing. That is, the functional style of
programming results in programs which are more easily rendered into
a parallel style. The evidence for this is to look at typical Common Lisp
programs and contrast their style and suitability for parallelization with
Scheme programs.

@b(4. Political Reasons for the Merger)

@b(4.1 The Scheme Community)

In the US there are two major Lisp communities - Common Lisp and Scheme.
These two communities overlap in terms of people who are proponents of
one of the other dialects depending on the context. For example, Gabriel
is a strong commercial proponent of Common Lisp, yet his own parallel
Lisp research is performed using Scheme as a workbench and starting point.

If Common Lisp were to abandon the 2-namespace situation, it would then be
easier to develop a layered definition in which Scheme is the base layer
and Common Lisp is the `industrial strength' layer. Scheme would then be
the natural subset for use on smaller computers and embedded systems.

One would have to careful to not constrain the Scheme community from
having to stick too closely to the definition of Scheme which would be this
fundamental layer. In addition, the Scheme community would need to be
convined that this layering is desirable. Though the entire Scheme community
was not present at any such discussions, Gerry Sussman and Will Clinger
seemed amenable at the last meeting.

@b(4.2 The European Community)

This community will, for the moment, be discussed as if it coincided with
the EuLisp group. This assumption is not, of course, correct, and later we
will argue that that fact can be used to justify retaining the 2-namespace
Common Lisp.

The EuLisp group is endeavoring to define a new standard for Lisp - possibly
to be proposed to the ISO community as a standard for Lisp. Their approach is
to take only lessons from the past rather than designs from other dialects of
Lisp. They wish to propose a 3 level standard in which the lowest level,
level 0, is the minimal Lisp, possibly suitable for proving properties of
Lisp programs. The second level, level 1, is of the size and extent of Scheme
and is intended as the right size for small personal computers.
The highest level, level 2, is about of the size and extent of Common Lisp.
It is intended as the industrial strength Lisp with a number of as-of-now
unspecified environmental features.

Rather than building on existing specifications, this group is starting afresh,
with all the concommitant social pressures of developing a standard using a
slightly too large working group. Key member of this group are Jerome Chailloux,
Julian Padgett, John Fitch, Herbert Stoyan, Attardi, and Jeff Dalton.

The key differences between EuLisp as it now stands and Common Lisp
is a single namespace and simple lambda-lists (no &optionals or keywords)
for EuLisp. At one face-to-face meeting, Chailloux and Padgett stated that
if Common Lisp were to collapse the two namespaces, they would be willing to
adopt fancy lambda-lists. These two concessions are possibly enough to
lay the groundwork for a widespread set of compromises, mostly from them,
on the merger of the two communities.

Without this technical merger, a battle is at hand. It appears that the
convenorship for ISO Lisp will go to France, with the US annoucning its
intentions of taking a technical leadership position. ANSI appears to want
assuage the European community by throwing a language to them for convenorship;
Lisp is the unfortunate victim.

If the US wanted the convenorship, it might wrestled from France. Bob Mathis
comments that it is often easier to bend a standard in one's own direction
when technical rather than political leadership is taken.

@b(4.3 The Lisp Community has a Better Tune)

Currently when Lisp vendors are asked how to run Lisp code on small
computers, the answer is either that it isn't possible or that Scheme
is the recommended Lisp for this purpose. This story sounds as if Common Lisp
were not designed to meet commercial needs, because most of the commerical
world uses small computers. If Scheme could be incorporated as a subset
or as a fundamental lower level, the story would be that one could run
Common Lisp, level 0 (that is, Scheme).

@b(5. Technical Reasons Against the Merger)

@b(5.1 Number of Namespaces)

There are really a larger number of namespaces than the two being
discussed here. The interpretation of a symbol in a Common Lisp will
still depend on the context to disambiguate variables from symbols from
type names and so on.

@b(5.2 Macros and Name Collisions)

Macros in Common Lisp are currently written in such a way that
functional variables are assumed constant. That is, suppose there is
a macro defined like this:
@Begin(Example)
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO ,THINGS))
@END(Example)
Here FOO is quoted, THINGS is taken from the parameter list for
the macro, but LIST is free. The macro writer has either assumed
that the referent of LIST in the environment in which the macro
expansion will appear is correct (this is not very likely), or else
he has assumed that LIST is a constant (this is probably the case).

If the programmer writes
@BEGIN(Example)
...
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
@End(Example)
in a single-namespace Common Lisp, it is likely that there is
a bug in the code.

Here is another example:
@Begin(Example)
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
...
(DEFMACRO TEST-CAR (CAR TEST-LIST)
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
@End(Example)

In some Scheme implementations it is possible to write the following:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(',CAR ,LIST))
@End(Example)

This is syntactically more tedious and that would have to be weighed.
Nevertheless, this proposal doesn't answer all technical problems.  When
uses of this macro is compiled to a file, the object that is output for
the reference to CAR is probably a representation of the procedure object
(compiled code object) for CAR. Possibly not all Common Lisp implementations
are set up to handle the case of outputting a compiled-code object to a
file and then reading it back in.

Consider this piece of code:

@Begin(Example)
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))
(FOO 3 Z)
@End(Example)

For each use of this macro there may be a separate copy of the
compiled code for the anonymous function in the macro definition.
Some systems are able to collapse structurally equal compiled-code
objects into only one copy when the occurrences of them are in one
file, but this is a non-trivial means of solving part of the problem
with the approach.

The real problem for Lisp implementors to make this approach workable
is that the compiler ought to open-code the original CAR operation
in the TEST-CAR code rather than to code a function call to CAR.
Thus, the compiler will need to be modified to recognize this idiom.

Another solution to the macro problem is presented by Kohlbecker in his
recent PhD thesis from Indiana. Macros can be written in a style that is
like the current Common Lisp style, but free function position variables
can be defaultly taken to be the globally defined function of the same name.

[Clinger is writing a proposal based on Kohlbecker's stuff.]

A third part of the solution is to include a new declaration form which
declares function definitions constant, and all Common Lisp implementations
can declare all Common Lisp functions constant. The correct behavior is to
signal an error when cases like TEST-CAR above example occur.

Though this seems like a potentially insurmountable problem - the Scheme
community has not defined a standard macro facility for Scheme because of
this problem - Common Lisp already has this problem, but people do not
notice it very much. Here is an example:

@BEGIN(Example)
(DEFMACRO FOO (X Y) `(CONS 'FOO (CONS ,X (CONS ,Y NIL))))

(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
@END(Example)

(BAZ 1 2) returns (((NIL . 2) . 1) . FOO), even though it seems that
(FOO 1 2) was intended by the programmer (except I, rpg, expected exactly
what happened).

On some Common Lisp implementations one can write:

@BEGIN(Example)
(DEFMACRO FOO (X Y) ;take a deep breath
 `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))

(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
@END(Example)

And (BAZ 1 2) will evaluate to (FOO 1 2), just, um, as everyone expected.
Note that this only works in some implementations of Common Lisp.

Perhaps it is the case that most programmers do not use FLET and LABELS,
though I know of several major user groups who do.

@b(5.3 Space Efficiency)

If a symbol is used both for its value and as a function, it currently costs no
additional space. Any program which has symbols which are used to denote 
distinct functions and values, however, would have to be changed. In general,
this means that some new symbols would be introduced. In most cases, the number
of new symbols introduced would not be extremely large, but there might be
pathological applications where there were exceptions. In the Lucid Lisp system,
there are 14 of these symbols, and the value cell is being used, in these cases,
as a cache for an object related to the function. 

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to an existing
data structure that already has on the order of 5 - 10 cells anyway.

Resolving the name conflicts that would result if functions and variables
were in the namespace would usually require the creation of additional
symbols.

@b(5.4 Time Efficiency)

In Common Lisp, a function call to a function associated with a symbol
involves indirecting through the symbol's function cell. A typical
implementation on stock hardware will look at the symbol's function cell,
which points to a piece of code, possibly with an intermediate pointer
through a procedure object, as in S-1 Lisp. An optimization to this is for
a function call to jump directly to the correct code object, perhaps
indirecting through a link table of some sort, but eliminating the
indirection through the symbol's function cell.  In order for DEFUN and
(SETF (SYMBOL-FUNCTION...)...)  to cause existing running code to work,
the operation of changing a symbol's function cell will invalidate the
link table or otherwise cause the correct new link to be made.

To use this same optimization in a single namespace Lisp, SETQ, rather
than (SETF (SYMBOL-FUNCTION...)...) must do the invalidating or re-linking.
The common case is that there is not a function associated with a symbol -
programmers do not often write code that changes function definitions
in inner loops - and so a flag stating there is no function definition
involved will need to be checked on each SETQ. 

Of course, only SETQs of symbols need to be checked, so that there could be
a test and branch added to SETQ, where SETQ might have been a single
instruction before. On some stock hardware, tricks with the addressing hardware
and word alignment can be played to make this fast in the non-functional value
case, but in fact it seems unlikely that this could cause any more than
a 10% degradation in the most pessimistic inner loop, and overall it is
unlikely to cause more than a 1% degradation in a large system.

@b(5.5 Cultural Compatibility)

We have encouraged the naming convention of *...* around global names.
If there were a single namespace, then this convention would need to
be altered to mean than a symbol had a value that was not a global
function definition.

@b(5.6 Special Variable Warnings)

If a single namespace were adopted, symbols naming functions would be,
technically, special variables, and, hence, compilers would normally warn
about them. There are two solutions to this: one is to declare such
functions as constant, and perhaps DEFUN could do this defaultly; the other
is to adopt the notion of a global lexical environment. More will be said
later about global lexical environments.  

There would also need to be a non-constant declaration defined, so that
function names can be dynamically scoped.

@b(5.7 Compatibility Issues)

Making a transition to a world with unified a function/value cell would
involve a considerable amount of incompatibility.

@b(5.7.1 Changing existing code)

Large bodies of code already exist which make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which might be non-trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100% reliability in any automatic way. Compilers could be
modified to provide the user information about conflicts as they come up
as a sort of machine-gun approach to the problem.

@b(5.7.2 Compatibility packages)

Various compatibility schemes have been proposed which would allow these
problems to be moderated, but not eliminated, by compatibility packages.
The simplist idea is to have a single Common Lisp with the single
namespace but with a compiler switch that allows two-namespace code to run
in this image.  Symbols would have function cells, but possibly represented
as properties on property lists.  All old Common Lisp code of the form:

@BEGIN(Example)
(F ...)
@END(Example)

would be modified to this:

@BEGIN(Example)
(FUNCALL #'F ...)
@END(Example)

where FUNCTION would look things up in the `function cell.' FUNCALL would
be retained in the compatability package. A bigger example is more convincing:

@BEGIN(Example)
(LET ((LIST ...))
 (LIST ...))
@END(Example)

becomes

@BEGIN(Example)
(LET ((LIST ...))
 (FUNCALL #'LIST ...))
@END(Example)

Possibly some compilers already perform this transformation internally and
will be simplified after the change. And perhaps an implementor will want
to provide a real function cell for this compatability in order to run old
code relatively fast. Lisps that normally have link tables will need to
provide separate linking code (possibly the old link code) for the
compatibility package.

[KMP: I believe that the scheme proposed above is immune to your
argument below, because the compatibility package simulates the old
Common Lisp.]

[The problem is that the compilers and other program-understanding programs
might be fooled by such compatibility things. For example, such programs
may have built-in assumptions about the function cell and value cell being
distinct and may not realize that a store into the value cell in one place
will perturb a later access to the function cell, which it may believe it has
proven could not be changed in a certain interval of code.]

@b(5.8 Compatibility with Scheme)

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. On the other hand, if all other things are equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

However, all other things are not equal. For example, there is an installed
base of code which would require changing. 

Even if compatibility with Scheme was achieved on this point, there is
currently no iron-clad guarantee that Scheme will not later change in an
incompatible way that will coincidentally thwart such a good faith move on
the part of Common Lisp. It is an explicit goal of the Scheme designers
[ref R↑3 Report] that Common Lisp compatibility not be uppermost in the
list of concerns.  That should weigh in.

On the other hand, the Scheme designers believe that Common Lisp has a
number of bad warts - two namespaces being foremost - and that, therefore,
compatability is not as important as it would be if the foundations of
each dialect were more closely akin. With the willingness of the Common
Lisp community to `see the light,' perhaps the willingness to remain
compatible with the newer, merged dialects, would be greater.

If compatability with Scheme is desired, there are other changes to Common
Lisp that are necessary or desirable. Foremost is CALL/CC, in which
first-class continuations are supported. This change would be completelty
upwards compatible and is not conceptually hard to implement; but, there
are many details and it is not easy to implement.

@b(5.9 Other Changes to Common Lisp to Accomodate the Merger)

A free variable in Common Lisp is taken to be a dynamic rather than
a lexical reference. This is because there is no global lexical environment
in Common Lisp. If this is the code

@BEGIN(Example)
(DEFUN FOO (X)(+ X Y))
@END(Example)

the reference to Y is special (dynamic). On the surface, in a
single-namespace Lisp, the reference to `+' is free also, and so it is
special (dynamic). One proposed solution is to make the default be lexical
(global), which makes Y refer to the global value for Y, and `+' to the
global definition of `+.'

Thus, there would be a global lexical environment in which symbols
that are used freely would be accessed. Currently there is a global
dynamic environment.

This further change would require users to modify their code, the
change being to, possibly, add some SPECIAL declarations.

@b(6. Political (non-technical) Reasons Against the Merger)

@b(6.1 The Lisp Community is Changing its Tune)

The Lisp vendors have convinced the commercial world that the Lisp
community has decided to get its act together and settle on one dialect of
Lisp - Common Lisp - and that it is time to start writing commercial
products using that dialect. If the Lisp community now changes Common Lisp
in such an incompatible way, then the newly-convinced commercial world
might balk.

Perhaps winning the single namespace battle loses the Lisp war.

On the other hand, if X3 is sanctioning this change as part of not
only a US standard Lisp, but an international standard Lisp, perhaps
the change will be excused.

@b(6.2 Can Vendors Afford the Merger?)

Most Lisp vendors have their hands full improving and honing their
products. Typically these vendors schedule tasks 6 months to a year ahead.
At the very least, if the merger takes n man-months to accomplish for some
vendor, there are n man-months of something else very useful that does not
get done.  If the task of the merger is on the order to of several
man-years for a vendor, that vendor might not survive the change.  If
there are such vendors, then the legal protections of CBEMA for members
will be tested.

Gabriel has estimated that at Lucid about 2 man-months are needed to
make the change initially followed by 4 man-months of shakedown.

Vendors like Symbolics will have a lot more work to do to convert their
own system to a single namespace, though they might use the compatability
scheme mentioned above.

@b(6.3 Can Users Afford the Merger?)

Many users have a lot of Common Lisp code now. Symbolics users are not
reacting well to the switchover to Common Lisp in Release 7, though it was
known for several years that the change would happen. A similar flag day
would be required for the switchover to the single namespace world, but on
a larger scale. [KMP: how expensive was it to manage the switchover?]

Again, perhaps X3 can help by conditioning users for the switchover, and
perhaps DARPA can pay for tools to help users; for example, a codewalker
could be written that could used to parse files and to report places in
the code that require attention.

@b(6.4 The Japanese Community)

The Japanese community seems to want to stick with Common Lisp pretty much
as it is today, according to reports from Prof. Ida. It appears that there
is a heavy commitment to the current definition in the commercial marketplace
there. The political issue seems to be that we will have a battle at the ISO
level regardless of the decision we make.

@b(6.5 Common Lisp can Win the ISO Fight Anyway)

The European Lisp community comprises a number of large and influential
computer manufacturers, many of whom are being convinced that Common Lisp
is a good commercial standard. The US Common Lisp community, including the
large manufacturers who are consumers of Common Lisp, can help persuade these
European manufacturers that a from-whole-cloth Lisp will not make a good
standard, and that the Europeans will be using a standard that is not used
in the US or Japan.

To accomplish this, though, requires some fancy lobbying and politicizing,
to which the Common Lisp community would need to commit.

@b(7. Summary)

There are compelling technical and non-technical reasons on both sides
of the issue. This white paper is an attempt to outline them so that
an informed decision can be reached.

∂08-Nov-86  0013	willc%tekchips.tek.csnet@RELAY.CS.NET 	Re: Draft  
Received: from RELAY.CS.NET by SAIL.STANFORD.EDU with TCP; 8 Nov 86  00:12:58 PST
Received: from tektronix by csnet-relay.csnet id aa11613; 8 Nov 86 2:47 EST
Received: by tektronix.TEK (5.31/6.16)
	id AA15786; Fri, 7 Nov 86 13:29:44 PST
Received: by tekchips.TEK (5.31/6.16)
	id AA00673; Fri, 7 Nov 86 13:29:13 PST
Message-Id: <8611072129.AA00673@tekchips.TEK>
To: RPG@SU-AI.ARPA
Cc: willc%tekchips.tek.com@RELAY.CS.NET
Subject: Re: Draft
Date: 07 Nov 86 13:29:03 PST (Fri)
From: willc%tekchips.tek.csnet@RELAY.CS.NET

My comments are delimited by "[!!" and "!!]".

@center(@b[Issues of Separation in Function Cells and Value Cells])

@center(@b[by RPG and KMP, etc.])

@b(0. Notation and Terminology) 

[!! Although I understand that many of these definitions are rooted in
Common Lisp's current terminology, I believe several of them serve only
to confuse the issue.  I believe the paper would be simplified by using
better definitions, which I offer in various places below.  I indicate
a few places in the paper where the presentation could be improved by
using these definitions, but I did not try to indicate all such places.
!!]

In this white paper we will use the following terminology. A `function' is
anything that can be APPLYed or FUNCALLed. A `non-function' is any other
Lisp object. We say that `a function, F, is associated with the symbol, S'
to mean that a pointer to the functional object, F, is stored in the
symbol-function cell of the symbol, S. We say that `a function, F, is
associated with the variable, V' to mean that a pointer to the function,
F, is stored as the value of the binding for the variable, V, and that the
variable, V, is meaningful only in a functional setting (the car position
of a combination or as the argument of FUNCTION). Functions become
associated with variables using FLET, LABELS, and MACROLET only. Functions
become associated with symbols using DEFUN and (SETF (SYMBOL-FUNCTION
...)...). We say that `a symbol or a variable, SV, has as its value the
function, F' to mean that the value cell of the symbol, SV, or the value
part of the binding for the variable, SV, contains a pointer to the
function, F.

[!! The definition of "function" in Common Lisp is hopeless, but that's
not your fault.  The above paragraph, however, needlessly reinforces the
confusion between environments and evaluation rules that must occur in
the minds of most people who try to learn Common Lisp.  Even
I am confused.  For instance, it appears to be legal to say
(PROGN (SETF (SYMBOL-FUNCTION 'FOO) 'BAR) (FOO X)) in Common Lisp.  What
is the meaning of this?  I assume Common Lisp has the "evaluate the car
position until you get a SUBR or a LAMBDA or a..." lossage, but I don't
know.

Suppose I say (SETF (SYMBOL-FUNCTION 'FOO) 'BAR).  Do you really intend
the above paragraph to say that "a pointer to" the symbol BAR is stored
in the function cell?  Similarly, do you really intend to say "a pointer
to" a lambda expression?

I don't understand "the variable, V, is meaningful only in a functional
setting".  If by V you mean an identifier (as is implied by the last
sentence of the paragraph), then what you say is incorrect because I
can certainly use the identifier in a SETQ (for example).  If by V you
mean a location, then I think it would be better to say that the
variable can be referenced only in a functional setting.  This should
be clarified.

It would be better to use the notion of a "procedure" as in Scheme.  It
would probably be sufficient to define a procedure to be an X such that
(AND (FUNCTIONP X) (NOT (SYMBOLP X)) (NOT (LISTP X))).
!!]

The `functional position' of a combination is the first element in a list
that is to be used as an expression to evaluate or to compile. (Other people
say that the functional position is `the car of the form.')  [!! Also
place expressions, et cetera, alas. !!]

A `name' is either a symbol or a variable.  [!! From which I infer that
a "variable" is an identifier that has been bound lexically.  See the
related comment above. !!]

A `namespace' is a mapping between names and objects.  There are two
namespaces with which we are concerned: the functional namespace and the
value namespace. To be particular, given a name which names a function,
the functional namespace is the mapping that yields the function named by
the name; given a name which names a value, the value namespace is the
mapping that yields the value associated with the name.  The functional
and value namespaces are distinct because, give a single name, the
functional namespace mapping and the value namespace mapping can yield
distinct objects. Note, the two namespaces might yield the same object,
but for definitional purposes, this happenstance is coincidental.

[!! You would be far better off to talk about environments, which are
mappings from identifiers to things (possibly objects), and about
evaluation rules, which are mappings from expressions and contexts to
results or answers.  The paragraph above makes it sound like a namespace
is an environment, but two sentences below you contradict yourself and
make a namespace into an evaluation rule.  This confusion persists
throughout the position paper. !!]

The functional namespace mapping is from names to functions; the value
namespace mapping is from names to Lisp objects, which includes functions.

The domain of the functional namespace also includes forms which look like
this:

	(lambda ...)

The functional namespace mapping is (FUNCTION <name>) and can be abbreviated
as #'<name>.

The value namespace mapping is (EVAL <form>). Lambda-expressions are not
in the domain of the value namespace mapping in Common Lisp.

[!! Doesn't this make it clear that you are using the word "namespace" to
mean an evaluation rule? !!]

@b(1. Introduction)

In 1981 the emerging Common Lisp community turned to Scheme for some of
its motivation and inspiration. Adopting lexical scoping proved one of the
most important decisions the Common Lisp group every made.  One aspect of
Scheme left behind was the unification of the function and value
namespaces.

The Common Lisp community is now faced with the fact of the existence of
three Lisp communities:  Common Lisp, Scheme, and EuLisp. The latter two
communities have adopted a unified function and value namespace; Common
Lisp has not. The question is whether it is feasible at this point for the
Common Lisp community to change its stand on this point - to merge the two
namespaces - and to merge the Lisp communities.

Before attempting to make any decision on the subject, the Common Lisp
community felt it important to clearly document both sides of the issue
in an unbiased way.

@b(2. Background)

Historically, most Lisp dialects have adopted a 2-namespace approach to
the naming problem. Largely this is because most dialects followed Lisp 1.5
unless there was some interesting reason not to follow it.

[!! I believe this to be a gross distortion of history, caused by the
confusion you have introduced between environments and evaluation rules.
I looked at the interpreter in the Lisp 1.5 in Appendix B of the Lisp
1.5 programmer's manual, and it is quite clearly using one environment
with two evaluation rules.  The separate environment was added later
as an efficiency hack to cope with deep binding.  After shallow binding
was invented, a few Lisps (e.g. Univac 1100 Lisp) went back to one
environment, but the mainstream did not because dynamic binding impeded
modularity and compilability.  The return to a single environment was
not really desirable until Scheme turned to lexical scope rules in 1975.
!!]

In Lisp 1.5, functions could be defined be [!! by !!] LABEL or be associated
with a
symbol. LABEL is like Common Lisp LABELS, and it was used to define
recursive functions which were associated with variables exactly as
values were associated with variables - on an a-list. McCarthy says that
LABEL was used infrequently, because functions were put on the property
lists of symbols, under a property name like SUBR. The terminology in the
Lisp 1.5 Programmer's Manual is that a ``symbol stands for a function.''

[!! I believe the above paragraph is irrelevant. !!]

On the other hand, Lisp 1.5 had nothing like FUNCALL; MAPLIST was defined
like this:

(DEFUN MAPLIST (X FN)
 (COND ((NULL X) NIL)
       (T (CONS (FN X) (MAPLIST (CDR X) FN)))))

In our terminology, Lisp 1.5 had two distinct namespaces, but they
coincided on the domain of variables. That is, given a variable as a name,
the value namespace mapping and the function namespace mapping are
identical.

[!! Wouldn't it be better to say that: Lisp 1.5 had a single environment
but two evaluation rules.  The evaluation rules coincided for identifiers.
(In Appendix B the rules are called apply and eval.  Actually there was a
third evaluation rule, evalquote, that was used only at top level.)

@b(3. Technical Reasons for the Merger)

@b(3.1 Notational Simplicity)

Many people believe that having the function position be evaluated
differently than the argument positions in Lisp is very inelegant.

[!! This is an argument against having separate evaluation rules.  It is
relevant because you can't reasonably have separate environments without
separate evaluation rules. !!]

This feature has the indirect effect of making the notation more
complicated in order to allow two things:  1. taking a name, using the
value namespace mapping to yield a value which happens to be a function,
and invoking that function; 2. taking a name, using the function namespace
mapping to yield a function, and using that function exactly like any
other Lisp object.

[!! The phrase "in order to allow" makes it sound as though the feature
was designed for the purpose of allowing people to do the two things,
but the point is that the features hinders people from doing the two
things.  The two things could be better phrased as:  1.  Fetch the value
of an identifier in the value environment and call it, hoping it is a
function.  2.  Fetch the value of an identifier in the function
environment and do anything except call it (e.g. pass it as an argument).
!!]

To call a function which is the value of a variable (or the result
of some other normally evaluated expression), one must use
the @t(FUNCALL) function. For example, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
@End(Example)
In a single namespace Lisp, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
@End(Example)

To pass an argument which is obtained by the rules of functional
evaluation, you currently must use the @t(FUNCTION) special form.
For example, one might write:
@Begin(Example)
(MAPC (FUNCTION PRINT) '(A B C D))
@End(Example)
or
@Begin(Example)
(MAPC #'PRINT '(A B C D))
@End(Example)
If there were a single namespace, one might write:
@Begin(Example)
(MAPC PRINT '(A B C D))
@End(Example)
The differences are more striking in a larger, more complex
example. In Common Lisp one writes:
@BEGIN(Example)
(DEFUN Y (F)
 (LET ((G #'(LAMBDA (H)
             #'(LAMBDA (Z)
                (FUNCALL (FUNCALL F (FUNCALL H H)) Z)))))
  #'(LAMBDA (X)
     (FUNCALL (FUNCALL F (FUNCALL G G)) X))))
@END(Example)
while in a single namespace Common Lisp, one would write:
@BEGIN(Example)
(DEFUN Y (F)
 (LET ((G (LAMBDA (H)
           (LAMBDA (Z) 
            ((F (H H)) Z)))))
  (LAMBDA (X) ((F (G G)) X))))
@END(Example)
which anyone can see is much simpler.

Probably few people would deny that the syntax resulting from the this
change would make the language appear better visually. If the issue were
being decided purely on the basis of cosmetics, probably few people
would oppose the change.

@b(3.2 Multiple Denotations for a Single Name)

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose a programmer has defined a function @t(F) as:
@Begin(Example)
(DEFUN F (X) (+ X 1))
@End(Example)
Then suppose he is writing a new function @t(G) and he wants it to
take a functional parameter @t(F) which it is to apply to its other argument.
Suppose he writes:
@Begin(Example)
(DEFUN G (F) (F 3))
@End(Example)
Issues of defined program semantics aside, it's probably obvious that the
programmer who wrote this piece of code meant to call the function named
by the formal parameter @t(F) on the argument @t(3). 
In Common Lisp, this function will ignore its arguement named @t(F) and
simply invoke the globally defined function named @t(F) on 3.

Unfortunately, not all situations are as clear cut as this. For example, 
in the following example:
@Begin(Example)
(DEFUN PRINT-SQRTS (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)
In this example, there are three uses of the name @t(LIST). The first is in
the bound variable list. The second is in initialization of the @t(DOLIST) 
variable. The third is in the @t(PRINT) expression. This program, which is
valid in current Common Lisp, would not be valid in a Common Lisp where 
functional and argument positions were evaluated in the same way. A common
thing to write instead would be:
@Begin(Example)
(DEFUN PRINT-SQRTS (LST)
  (DOLIST (ELEMENT LST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)

As should be clear from these examples, the advantage of treating the
function and argument positions the same is that using parameters as
functions is made more convenient syntactically.

The disadvantage is that @i(not) using parameters as functions is made
less convenient syntactically, because parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions which will be needed in the function body.

[!! Here I would remark that parameter names must be carefully chosen
in any case to avoid shadowing the names of variables needed in the
body.  If, on the other hand, Common Lisp is thought of as a flat rather
than block-structured language, so that people who use LET, DO, and the
like are considered weird, then my remark has little force. !!]

In the function PRINT-SQRTS above, the parameter named LST is better named
LIST, though PRINT-SQRTS is not better named PRINT-SQUARE-ROOTS.

The following is a simple example of some of the important issues 
in variable naming:
@Begin(Example)
(DEFUN ODDITY-1 (LIST) (LIST LIST LIST))
(ODDITY #'CONS)
@End(Example)
Depending on which way the issue is decided, the possible return values from
this function are:
@Begin(Example)
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
@End(Example)

@b(3.3 Higher Order Functions are Possible)

Functions like the Y function above, which manipulate functions directly, are
more perspicuously written within a single namespace Lisp. The point is that
with two namespaces this style is not encouraged, while in a single namespace
Lisp it is encouraged.

[!! I think "not encouraged" should read "discouraged". !!]

@b(3.4 Abstraction Sharing)

In a single namespace Lisp, it is easier to define an abstract piece of
code that shares abstractions between data and functions. An example of
this is the abstract stream code in Chapter 4 of Abelson and Sussman, in
which it is shown how to write streams based either on functions or on data
structures.  Again, all of this is possible in Common Lisp as it stands,
but it is not an encouraged style. The problem is that it is a burden to
think about which namespace mapping will be in force for various
variables.

@b(3.5 Compiler Simplicity)

In current Common Lisp compilers, special cases code is used when
deciding which namespace mapping to use when a variable is
examined by the compiler. A single namespace Lisp will result in simpler,
smaller, faster compilers in some cases.

@b(3.6 Referential Clarity)

In a 2-namespace Lisp it is the case that without a context it is not
possible to decide whether the functional or the value namespace is the
proper one to use. These two forms result in different interpretations of
x:
@BEGIN(Example)
(x ...)
@END(Example)
@BEGIN(Example)
(... x ...)
@END(Example)
Unfortunately, the basic rule of Lisp style is violated, that rule being
that code is clear when the least amount of context is necessary to
determine what each expression does.

@b(3.7 Multiprocessing)

The functional style which is encouraged by single namespace Lisps
is conducive to multiprocessing. That is, the functional style of
programming results in programs which are more easily rendered into
a parallel style. The evidence for this is to look at typical Common Lisp
programs and contrast their style and suitability for parallelization with
Scheme programs.

@b(4. Political Reasons for the Merger)

@b(4.1 The Scheme Community)

In the US there are two major Lisp communities - Common Lisp and Scheme.
These two communities overlap in terms of people who are proponents of
one of the other dialects depending on the context. For example, Gabriel
is a strong commercial proponent of Common Lisp, yet his own parallel
Lisp research is performed using Scheme as a workbench and starting point.

If Common Lisp were to abandon the 2-namespace situation, it would then be
easier to develop a layered definition in which Scheme is the base layer
and Common Lisp is the `industrial strength' layer. Scheme would then be
the natural subset for use on smaller computers and embedded systems.

One would have to [!! be !!] careful [!! exchange the following words !!]
to not constrain the Scheme community [!! delete the following 2 words? !!]
from
having to stick too closely to the definition of Scheme which would be this
fundamental layer. In addition, the Scheme community would need to be
convined [!! or convinced !!]
that this layering is desirable. Though the entire Scheme community
was not present at any such discussions, Gerry Sussman and Will Clinger
seemed amenable at the last meeting.

@b(4.2 The European Community)

This community will, for the moment, be discussed as if it coincided with
the EuLisp group. This assumption is not, of course, correct, and later we
will argue that that fact can be used to justify retaining the 2-namespace
Common Lisp.

The EuLisp group is endeavoring to define a new standard for Lisp - possibly
to be proposed to the ISO community as a standard for Lisp. Their approach is
to take only lessons from the past rather than designs from other dialects of
Lisp. They wish to propose a 3 level standard in which the lowest level,
level 0, is the minimal Lisp, possibly suitable for proving properties of
Lisp programs. The second level, level 1, is of the size and extent of Scheme
and is intended as the right size for small personal computers.
The highest level, level 2, is about of the size and extent of Common Lisp.
It is intended as the industrial strength Lisp with a number of as-of-now
unspecified environmental features.

Rather than building on existing specifications, this group is starting afresh,
with all the concommitant social pressures of developing a standard using a
slightly too large working group. Key member of this group are Jerome Chailloux,
Julian Padgett, John Fitch, Herbert Stoyan, [!! Giuseppe !!] Attardi, and Jeff Dalton.

The key differences between EuLisp as it now stands and Common Lisp
is a single namespace and simple lambda-lists (no &optionals or keywords)
for EuLisp. At one face-to-face meeting, Chailloux and Padgett stated that
if Common Lisp were to collapse the two namespaces, they would be willing to
adopt fancy lambda-lists. These two concessions are possibly enough to
lay the groundwork for a widespread set of compromises, mostly from them,
on the merger of the two communities.

Without this technical merger, a battle is at hand. It appears that the
convenorship for ISO Lisp will go to France, with the US annoucning its
intentions of taking a technical leadership position. ANSI appears to want
assuage the European community by throwing a language to them for convenorship;
Lisp is the unfortunate victim.

[!! typos in the above paragraph: "annoucning", "want assuage".  In the
paragraph below: "wrestled".
!!]

If the US wanted the convenorship, it might wrestled from France. Bob Mathis
comments that it is often easier to bend a standard in one's own direction
when technical rather than political leadership is taken.

@b(4.3 The Lisp Community has a Better Tune)

Currently when Lisp vendors are asked how to run Lisp code on small
computers, the answer is either that it isn't possible or that Scheme
is the recommended Lisp for this purpose. This story sounds as if Common Lisp
were not designed to meet commercial needs, because most of the commerical
world uses small computers. If Scheme could be incorporated as a subset
or as a fundamental lower level, the story would be that one could run
Common Lisp, level 0 (that is, Scheme).

@b(5. Technical Reasons Against the Merger)

@b(5.1 Number of Namespaces)

There are really a larger number of namespaces than the two being
discussed here. The interpretation of a symbol in a Common Lisp will
still depend on the context to disambiguate variables from symbols from
type names and so on.

[!! There are four lexical environments: the value environment, the
function environment, the go tag environment, and the block exit
environment.  Having separate go tag and block exit environments in
Common Lisp doesn't matter much because go tags and block exits are not
first class values in Common Lisp.  Most of the arguments for removing the
function environment would apply to the go tag and block exit environment
only if go tags and block exits were replaced by first class values such
as Scheme's continuations. !!]

@b(5.2 Macros and Name Collisions)

Macros in Common Lisp are currently written in such a way that
functional variables are assumed constant. That is, suppose there is
a macro defined like this:
@Begin(Example)
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO ,THINGS))
@END(Example)
Here FOO is quoted, THINGS is taken from the parameter list for
the macro, but LIST is free. The macro writer has either assumed
that the referent of LIST in the environment in which the macro
expansion will appear is correct (this is not very likely), or else
he has assumed that LIST is a constant (this is probably the case).

If the programmer writes
@BEGIN(Example)
...
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
@End(Example)
in a single-namespace Common Lisp, it is likely that there is
a bug in the code.

Here is another example:
@Begin(Example)
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
...
(DEFMACRO TEST-CAR (CAR TEST-LIST)
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
@End(Example)

In some Scheme implementations it is possible to write the following:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(',CAR ,LIST))
@End(Example)

This is syntactically more tedious and that would have to be weighed.
Nevertheless, this proposal doesn't answer all technical problems.  When
uses of this macro is compiled to a file, the object that is output for
the reference to CAR is probably a representation of the procedure object
(compiled code object) for CAR. Possibly not all Common Lisp implementations
are set up to handle the case of outputting a compiled-code object to a
file and then reading it back in.

Consider this piece of code:

@Begin(Example)
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))
(FOO 3 Z)
@End(Example)

For each use of this macro there may be a separate copy of the
compiled code for the anonymous function in the macro definition.
Some systems are able to collapse structurally equal compiled-code
objects into only one copy when the occurrences of them are in one
file, but this is a non-trivial means of solving part of the problem
with the approach.

The real problem for Lisp implementors to make this approach workable
is that the compiler ought to open-code the original CAR operation
in the TEST-CAR code rather than to code a function call to CAR.
Thus, the compiler will need to be modified to recognize this idiom.

Another solution to the macro problem is presented by Kohlbecker in his
recent PhD thesis from Indiana. Macros can be written in a style that is
like the current Common Lisp style, but free function position variables
can be defaultly taken to be the globally defined function of the same name.

[Clinger is writing a proposal based on Kohlbecker's stuff.]
[!! I'm not going to worry about the problem of sending the compiler's
output to a file.  I do think that's a tough problem. !!]

A third part of the solution is to include a new declaration form which
declares function definitions constant, and all Common Lisp implementations
can declare all Common Lisp functions constant. The correct behavior is to
signal an error when cases like TEST-CAR above example occur.

Though this seems like a potentially insurmountable problem - the Scheme
community has not defined a standard macro facility for Scheme because of
this [!! and other !!]
problem - Common Lisp already has this problem, but people do not
notice it very much. Here is an example:

@BEGIN(Example)
(DEFMACRO FOO (X Y) `(CONS 'FOO (CONS ,X (CONS ,Y NIL))))

(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
@END(Example)

(BAZ 1 2) returns (((NIL . 2) . 1) . FOO), even though it seems that
(FOO 1 2) was intended by the programmer (except I, rpg, expected exactly
what happened).

On some Common Lisp implementations one can write:

[!! On my reading of CLtL this should work in all correct implementations.
(I used to assume that when I said something should work in "all
implementations", people would understand that I was speaking only of
correct implementations.  My experience with the Common Lisp community
has taught me otherwise.)  Page 86 says that quoted objects "may be any
Lisp object whatsoever", and I haven't seen any restrictions that prevent
macros from expanding into arbitrary code.  The Scheme standard, on the
other hand, is careful not to say that all objects can be quoted.
!!]

@BEGIN(Example)
(DEFMACRO FOO (X Y) ;take a deep breath
 `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))

(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
@END(Example)

And (BAZ 1 2) will evaluate to (FOO 1 2), just, um, as everyone expected.
Note that this only works in some implementations of Common Lisp.

Perhaps it is the case that most programmers do not use FLET and LABELS,
though I know of several major user groups who do.

@b(5.3 Space Efficiency)

If a symbol is used both for its value and as a function, it currently costs no
additional space. Any program which has symbols which are used to denote 
distinct functions and values, however, would have to be changed. In general,
this means that some new symbols would be introduced. In most cases, the number
of new symbols introduced would not be extremely large, but there might be
pathological applications where there were exceptions. In the Lucid Lisp system,
there are 14 of these symbols, and the value cell is being used, in these cases,
as a cache for an object related to the function. 

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to an existing
data structure that already has on the order of 5 - 10 cells anyway.

Resolving the name conflicts that would result if functions and variables
were in the namespace would usually require the creation of additional
symbols.

[!! This section is terribly biased.  It should describe the simple
calculation that determines which way takes less space.  Let N be the
number of symbols in a system, let S be the space occupied by the average
symbol in an implementation of Common Lisp as now defined, let S' be the
space occupied by the average symbol in an implementation of Common Lisp
as modified by merging the value and function environments, and let X be
the number of symbols that must be added to a system to resolve name
conflicts.  Then the space "saved" by having separate environments is
((N + X) * S') - (N * S).  For example, if N is 1000, X is 14, S' is 9,
and S is 10, then the space "saved" is -874.  That is, the separate
function environment would take up over 8% more space than the single
environment.  To a first approximation, the question is whether X / N
is larger than (S - S') / S'.  We know that the latter is roughly 10-20%,
and it seems that X / N will be greater than that only in pathological
cases, so the tone of this section is misleading. !!]

@b(5.4 Time Efficiency)

In Common Lisp, a function call to a function associated with a symbol
involves indirecting through the symbol's function cell. A typical
implementation on stock hardware will look at the symbol's function cell,
which points to a piece of code, possibly with an intermediate pointer
through a procedure object, as in S-1 Lisp. An optimization to this is for
a function call to jump directly to the correct code object, perhaps
indirecting through a link table of some sort, but eliminating the
indirection through the symbol's function cell.  In order for DEFUN and
(SETF (SYMBOL-FUNCTION...)...)  to cause existing running code to work,
the operation of changing a symbol's function cell will invalidate the
link table or otherwise cause the correct new link to be made.

To use this same optimization in a single namespace Lisp, SETQ, rather
than (SETF (SYMBOL-FUNCTION...)...) must do the invalidating or re-linking.
The common case is that there is not a function associated with a symbol -
programmers do not often write code that changes function definitions
in inner loops - and so a flag stating there is no function definition
involved will need to be checked on each SETQ. 

Of course, only SETQs of symbols need to be checked, so that there could be
a test and branch added to SETQ, where SETQ might have been a single
instruction before. On some stock hardware, tricks with the addressing hardware
and word alignment can be played to make this fast in the non-functional value
case, but in fact it seems unlikely that this could cause any more than
a 10% degradation in the most pessimistic inner loop, and overall it is
unlikely to cause more than a 1% degradation in a large system.

@b(5.5 Cultural Compatibility)

We have encouraged the naming convention of *...* around global names.
If there were a single namespace, then this convention would need to
be altered to mean than a symbol had a value that was not a global
function definition.

@b(5.6 Special Variable Warnings)

If a single namespace were adopted, symbols naming functions would be,
technically, special variables, and, hence, compilers would normally warn
about them. There are two solutions to this: one is to declare such
functions as constant, and perhaps DEFUN could do this defaultly; the other
is to adopt the notion of a global lexical environment. More will be said
later about global lexical environments.  

There would also need to be a non-constant declaration defined, so that
function names can be dynamically scoped.

@b(5.7 Compatibility Issues)

Making a transition to a world with unified a function/value cell would
involve a considerable amount of incompatibility.

@b(5.7.1 Changing existing code)

Large bodies of code already exist which make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which might be non-trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100% reliability in any automatic way. Compilers could be
modified to provide the user information about conflicts as they come up
as a sort of machine-gun approach to the problem.

@b(5.7.2 Compatibility packages)

Various compatibility schemes have been proposed which would allow these
problems to be moderated, but not eliminated, by compatibility packages.
The simplist idea is to have a single Common Lisp with the single
namespace but with a compiler switch that allows two-namespace code to run
in this image.  Symbols would have function cells, but possibly represented
as properties on property lists.  All old Common Lisp code of the form:

@BEGIN(Example)
(F ...)
@END(Example)

would be modified to this:

@BEGIN(Example)
(FUNCALL #'F ...)
@END(Example)

where FUNCTION would look things up in the `function cell.' FUNCALL would
be retained in the compatability package. A bigger example is more convincing:

@BEGIN(Example)
(LET ((LIST ...))
 (LIST ...))
@END(Example)

becomes

@BEGIN(Example)
(LET ((LIST ...))
 (FUNCALL #'LIST ...))
@END(Example)

Possibly some compilers already perform this transformation internally and
will be simplified after the change. And perhaps an implementor will want
to provide a real function cell for this compatability in order to run old
code relatively fast. Lisps that normally have link tables will need to
provide separate linking code (possibly the old link code) for the
compatibility package.

[KMP: I believe that the scheme proposed above is immune to your
argument below, because the compatibility package simulates the old
Common Lisp.]

[The problem is that the compilers and other program-understanding programs
might be fooled by such compatibility things. For example, such programs
may have built-in assumptions about the function cell and value cell being
distinct and may not realize that a store into the value cell in one place
will perturb a later access to the function cell, which it may believe it has
proven could not be changed in a certain interval of code.]

[!! I agree with whoever wrote "[KMP: I believe...".  This was the substance
of my claim that existing Common Lisp code could be mechanically converted
to the future (?) semantics. !!]

@b(5.8 Compatibility with Scheme)

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. On the other hand, if all other things are equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

However, all other things are not equal. For example, there is an installed
base of code which would require changing. 

Even if compatibility with Scheme was achieved on this point, there is
currently no iron-clad guarantee that Scheme will not later change in an
incompatible way that will coincidentally thwart such a good faith move on
the part of Common Lisp. It is an explicit goal of the Scheme designers
[ref R↑3 Report] that Common Lisp compatibility not be uppermost in the
list of concerns.  That should weigh in.

On the other hand, the Scheme designers believe that Common Lisp has a
number of bad warts - two namespaces being foremost - and that, therefore,
compatability is not as important as it would be if the foundations of
each dialect were more closely akin. With the willingness of the Common
Lisp community to `see the light,' perhaps the willingness to remain
compatible with the newer, merged dialects, would be greater.

If compatability with Scheme is desired, there are other changes to Common
Lisp that are necessary or desirable. Foremost is CALL/CC, in which
first-class continuations are supported. This change would be completelty
upwards compatible and is not conceptually hard to implement; but, there
are many details and it is not easy to implement.

[!! The official and more descriptive name is
call-with-current-continuation.  I would say that tail recursion is the
most important compatibility issue after the single environment, but
like call-with-current-continuation it is "completely" (note typo above)
upwards compatible and not hard to implement.
!!]

@b(5.9 Other Changes to Common Lisp to Accomodate the Merger)

A free variable in Common Lisp is taken to be a dynamic rather than
a lexical reference. This is because there is no global lexical environment
in Common Lisp. If this is the code

@BEGIN(Example)
(DEFUN FOO (X)(+ X Y))
@END(Example)

the reference to Y is special (dynamic). On the surface, in a
single-namespace Lisp, the reference to `+' is free also, and so it is
special (dynamic). One proposed solution is to make the default be lexical
(global), which makes Y refer to the global value for Y, and `+' to the
global definition of `+.'

Thus, there would be a global lexical environment in which symbols
that are used freely would be accessed. Currently there is a global
dynamic environment.

This further change would require users to modify their code, the
change being to, possibly, add some SPECIAL declarations.

@b(6. Political (non-technical) Reasons Against the Merger)

@b(6.1 The Lisp Community is Changing its Tune)

The Lisp vendors have convinced the commercial world that the Lisp
community has decided to get its act together and settle on one dialect of
Lisp - Common Lisp - and that it is time to start writing commercial
products using that dialect. If the Lisp community now changes Common Lisp
in such an incompatible way, then the newly-convinced commercial world
might balk.

Perhaps winning the single namespace battle loses the Lisp war.

On the other hand, if X3 is sanctioning this change as part of not
only a US standard Lisp, but an international standard Lisp, perhaps
the change will be excused.

@b(6.2 Can Vendors Afford the Merger?)

Most Lisp vendors have their hands full improving and honing their
products. Typically these vendors schedule tasks 6 months to a year ahead.
At the very least, if the merger takes n man-months to accomplish for some
vendor, there are n man-months of something else very useful that does not
get done.  If the task of the merger is on the order to of several
man-years for a vendor, that vendor might not survive the change.  If
there are such vendors, then the legal protections of CBEMA for members
will be tested.

Gabriel has estimated that at Lucid about 2 man-months are needed to
make the change initially followed by 4 man-months of shakedown.

[!! Person-months, please. !!]

Vendors like Symbolics will have a lot more work to do to convert their
own system to a single namespace, though they might use the compatability
scheme mentioned above.

@b(6.3 Can Users Afford the Merger?)

Many users have a lot of Common Lisp code now. Symbolics users are not
reacting well to the switchover to Common Lisp in Release 7, though it was
known for several years that the change would happen. A similar flag day
would be required for the switchover to the single namespace world, but on
a larger scale. [KMP: how expensive was it to manage the switchover?]

Again, perhaps X3 can help by conditioning users for the switchover, and
perhaps DARPA can pay for tools to help users; for example, a codewalker
could be written that could used to parse files and to report places in
the code that require attention.

@b(6.4 The Japanese Community)

The Japanese community seems to want to stick with Common Lisp pretty much
as it is today, according to reports from Prof. Ida. It appears that there
is a heavy commitment to the current definition in the commercial marketplace
there. The political issue seems to be that we will have a battle at the ISO
level regardless of the decision we make.

@b(6.5 Common Lisp can Win the ISO Fight Anyway)

The European Lisp community comprises a number of large and influential
computer manufacturers, many of whom are being convinced that Common Lisp
is a good commercial standard. The US Common Lisp community, including the
large manufacturers who are consumers of Common Lisp, can help persuade these
European manufacturers that a from-whole-cloth Lisp will not make a good
standard, and that the Europeans will be using a standard that is not used
in the US or Japan.

To accomplish this, though, requires some fancy lobbying and politicizing,
to which the Common Lisp community would need to commit.

@b(7. Summary)

There are compelling technical and non-technical reasons on both sides
of the issue. This white paper is an attempt to outline them so that
an informed decision can be reached.

/sub
"willc%tekchips.tek.csnet"@CSNET-RELAY
Draft

Will, thanks for your quickly-produced comments. There are some reactions
I have to them, though I pretty-much agree with you on reflection.  Rather
than presenting my reactions in a message, I will incorporate them into a
new draft, which I will send to you, tomorrow, I hope.

			-rpg-

I think the CSNET connection dropped a number of characters
in either your message or mine, because some of the stuff in
your returned copy looks funny. Perhaps some of the dropped letters
in words you mention are due to that. But this is unimportant.

The formalism I introduced into the paper with the notation section
was geared to being more precise than most Common Lispers are used
to, but not all the way to the most accurate. I suppose it's simply
a matter of deciding to what degree one should take formalism in this
forum.  I re-read the RRR Report yesterday, and I think you're style of
presentation misses some of the points that my notation is trying to
bring out. In Common Lisp, symbols play a larger and more prominent
role than in Scheme. For one thing, you can bind a symbol to get
dynamic binding in Common Lisp. The RRR Report treats them haphazardly
as compared with most other aspects of the language. 

My formalism is also geared towards emphasizing the reading of programs
by people, while yours concentrates on precise semantics qua semantics.

Let me answer some of your minor comments next.

This expression

(PROGN (SETF (SYMBOL-FUNCTION 'FOO) 'BAR) (FOO X))

signals an error. There is not evaluate-repeatedly-until rule in Common
Lisp. The symbol-function cell points to the symbol, BAR, which, I presume,
happens to not have a global function associated with it. Note also, that
the terminology ``function associated with ...'' is Common Lisp terminology.

I should point out that some Common Lisps (cough, cough, Lucid's in
particular) puts into the function cell a trampoline function that
essentially FUNCALLs the pointer you want to put there with the
(SETF (SYMBOL-FUNCTION ...)...), so that if you did (DEFUN BAR (X)...),
(FOO 3) would call BAR in the above example. I think this is a bug.

I should make precise the following: the world is broken up into variables
and symbols, each category being named by identifiers. I make this breakdown
because then dynamic binding is the simplest definition of how to bind
symbol values. So, when I say `the variable V,' I mean the non-symbol V.

When you have a function associated with a variable (lexical variable)
then it can only have been introduced with an FLET or a LABELS. If the
variable is V, then you had to have written one of

(labels ((v ...))...)

or 

(flet ((v ...))...)

In this case, if you write (setq v ...) within the scope of either of these,
that V does not refer to the functional lexical variable V. It is either a
reference to another variable named V or the symbol V.

I chose to define a namespace as a (mathematical) mapping to avoid having
to introduce environments and evaluations rules. Mappings are an
abstraction that covers both of those (unless I misunderstand), and I use
the term in that manner. My goal, again, was to go enough of the way
towards formalism to have precise terminology without going so far as to
confuse and while using Common Lisp terminology as far as possible.  Also,
I wanted to emphasize that the problem has to do with how, when confronted
with an identifier, to determine how to interpret it - in you terminology,
first what environment to use and second what evaluation rule to use,
which is purely a function of the environment.  If you think this didn't
work, we can fix it up.

I think the historical situation is more nearly as I said than what you
said, and the details are more gross than either one of us suggests.

Lisp 1.5 broke symbols into values and functions; values were stored on
the a-list, and functions on the property lists of symbols.  Reading the
interpreter you can see that different rules were used to get at the
different namespaces. When evaluating the function position of a
combination, the symbol's `function cell' was examined first.

Lisp 1.5 had both deep binding and shallow binding (!). The former was
invoked when you used (COMMON <vars>), and the latter when you used
(SPECIAL <vars>) in code to be compiled. Compiled functions communicated
with each other with special variables, and common variables were used to
communicate between compiled and interpreted code.  Greenblatt removed
COMMON from the PDP-6 Lisp and made SPECIAL work defaultly in the
interpreter, and thus he made the first `modern' shallow-bound Lisp.

When I quizzed McCarthy about the treatment of functions, he said all he
could remember was that they hacked it together so that the most obvious
things to do with functions worked. He said they had no theoretical
conception of how to treat them. The main concern was to make compiled
code and interpreted code work together.

[!! The phrase "in order to allow" makes it sound as though the feature
was designed for the purpose of allowing people to do the two things,
but the point is that the features hinders people from doing the two
things.  The two things could be better phrased as:  1.  Fetch the value
of an identifier in the value environment and call it, hoping it is a
function.  2.  Fetch the value of an identifier in the function
environment and do anything except call it (e.g. pass it as an argument).
!!]

The features happen to hinder people from doing some things, but the
features themselves were designed to enable people to win somehow.
In your re-phrasing of point 2, you can call the what-you-hope-is-a-function,
but by FUNCALLing it!

[!! Here I would remark that parameter names must be carefully chosen
in any case to avoid shadowing the names of variables needed in the
body.  If, on the other hand, Common Lisp is thought of as a flat rather
than block-structured language, so that people who use LET, DO, and the
like are considered weird, then my remark has little force. !!]

People who use LET, DO, and etc are considered normal.

[!! I think "not encouraged" should read "discouraged". !!]

``Discouraged'' seems to imply an intention by someone to design
something that discourages. This never happened, it was the case that
the majority of Common Lisp designers (Steele and I not included)
did not feel that this style of programming would be important, so
they chose to not encourage it. I believe that the style discourages,
yet I believe that `not encourage' is the most accurate wording.

On the macro defined like this:

(DEFMACRO FOO (X Y) ;take a deep breath
 `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))

All correct Common Lisp implementations will do the right thing when
compiling in memory, but I don't think that a correct implementation
has to be able to write and read such things from files during fasload.

[!! I agree with whoever wrote "[KMP: I believe...".  This was the substance
of my claim that existing Common Lisp code could be mechanically converted
to the future (?) semantics. !!]

I wrote that.